//
// Created by Dai Yan on 2022/1/6.
//
#include "UnicodeConv.h"

#include <deque>
#include <fstream>
#include <iostream>
#include <nlohmann/json.hpp>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

class Solution
{
    bool dfs(const vector<vector<int>> &M, int current, int target, int depth, int maxDepth, vector<bool> &visited, vector<int> &ans)
    {
        if (depth >= maxDepth)
            return false;

        if (current == target) {
            return true;
        }
        else {
            for (int next: M[current]) {
                if (visited[next])
                    continue;

                ans.push_back(next);
                visited[next] = true;
                if (dfs(M, next, target, depth + 1, maxDepth, visited, ans))
                    return true;
                ans.pop_back();
                visited[next] = false;
            }
        }
        return false;
    }

public:
    vector<int> find_path(const vector<vector<int>> &M, int a, int b, int maxDepth)
    {
        vector<int> ans;
        ans.reserve(maxDepth);
        vector<bool> visited;
        visited.resize(M.size(), false);
        ans.push_back(a);
        visited[a] = true;
        dfs(M, a, b, 0, maxDepth, visited, ans);
        return ans;
    }
};

/*
{
  "derivation": "语出《法华经·法师功德品》下至阿鼻地狱。”",
  "example": "但也有少数意志薄弱的……逐步上当，终至堕入～。★《上饶集中营·炼狱杂记》",
  "explanation": "阿鼻梵语的译音，意译为无间”，即痛苦无有间断之意。常用来比喻黑暗的社会和严酷的牢狱。又比喻无法摆脱的极其痛苦的境地。",
  "pinyin": "ā bí dì yù",
  "word": "阿鼻地狱",
  "abbreviation": "abdy"
}
*/

struct Idiom {
    string derivation;
    string example;
    string explanation;
    string pinyin;
    string word;
    string abbreviation;
    u32string word2;
    NLOHMANN_DEFINE_TYPE_INTRUSIVE(Idiom, derivation, example, explanation, pinyin, word, abbreviation)
};
using Idioms = vector<Idiom>;


void make_table(const string &fileName, Idioms &idioms, vector<vector<int>> &table)
{
    {
        std::ifstream in(fileName);
        auto doc = nlohmann::json::parse(in);
        in.close();
        idioms = doc;

        cout << doc[0] << endl;
    }

    for (auto &idiom: idioms) {
        ConvU8ToU32(idiom.word, idiom.word2);
    }

    map<char32_t, vector<int>> heads;
    for (int i = 0; i < idioms.size(); ++i) {
        const auto &idiom = idioms[i];
        heads[idiom.word2.front()].push_back(i);
    }

    table.resize(idioms.size());
    for (int i = 0; i < idioms.size(); ++i) {
        const auto &idiom = idioms[i];
        auto ch = idiom.word2.back();
        if (heads.count(ch)) {
            table[i] = heads[ch];
        }
    }
}


int main(int argv, char **argc)
{
    Idioms idioms;
    vector<vector<int>> table;
    make_table("../../idiom.json", idioms, table);

    map<u32string, int> ids;
    for (int i = 0; i < idioms.size(); ++i) {
        ids[idioms[i].word2] = i;
    }

    u32string word1;
    u32string word2;

    if (argv == 3) {
        ConvU8ToU32(argc[1], word1);
        ConvU8ToU32(argc[2], word2);
    }
    else {
        word1 = U"神机妙算";
        word2 = U"十全十美";
    }

    int from = ids.at(word1);
    int to = ids.at(word2);

    auto path = Solution().find_path(table, from, to, 10);

    if (!path.empty()) {
        for (int i = 0; i < path.size() - 1; ++i) {
            cout << idioms[path[i]].word << "(" << idioms[path[i]].derivation << ") -> ";
        }
        cout << idioms[path.back()].word << endl;
    }

    return 0;
}
